1. Field of the Invention
This invention relates to error detection in a digital transmission system.
2. Description of the Prior Art
U.K. Patent specification No. 1,281,390 describes methods and apparatus for testing digital data transmission systems. A method of error detection described in this specification comprises receiving from a transmitter a serial pattern of digits in which each digit, as transmitted, is a predetermined function of two or more digits each preceding that digit by a particular spacing in the pattern, and comparing a digit in the received pattern with the combination, in accordance with the said predetermined function, of two or more digits preceding that digit by the said particular spacing in the received pattern and generating an error indication when there is no correlation. The comparison is made for each digit in turn of the serial pattern (remembering, of course, that the comparison cannot commence immediately at the very beginning of the pattern because at that time there are no preceding digits). If a particular bit is in error it will become in turn, as time progresses, the said "digit in the received pattern" then one of each of the "two or more digits preceding that digit by the said particular spacing". That is to say the erroneous digit will be involved in three or more comparisons and (ignoring correlated errors which the comparison cannot detect) three or more error indications will be given. For this reason, a divider circuit is connected to the output of the means generating the error indication.
FIGS. 1 and 2 hereof reproduce the drawings appearing in U.K. Patent specification No. 1,281,390 and the following description is given in that specification:
FIG. 1 is a diagram of pseudo-random pattern generating apparatus forming part of the system, and
FIG. 2 is a diagram of error detecting apparatus forming part of the system.
The drawings illustrate apparatus for detecting errors in a binary digital data transmission system. A pseudo-random pattern of binary data is generated in the apparatus illustrated in FIG. 1 and is passed from the transmitter to the receiver of the system that is being tested. Errors in the received pattern are detected in the apparatus illustrated in FIG. 2, thereby enabling the probability of bit error in the transmission system to be measured.
The pseudo-random pattern generator (FIG. 1) is of conventional form and includes a shift register SRI having n stages SR1, SR2, . . . SRr, . . . SRn. The rth and nth stages of the register SRI have outputs to a modulo 2 adder ADD1 the output of which is connected back to the input of the register. The output of the register is transmitted over the system that is being tested.
When a suitable train of bits is stored in the shift register SRI the apparatus functions to generate a pseudo-random pattern of bits in which, under conditions of no error, any bit is correlated with the modulo 2 sum of the rth and nth preceding bits. The function of the register SRI is illustrated, by way of example, for the case n = 4 in the Table I set out below. In this Table it is assumed that the third and fourth stages of the register are connected to the input of the modulo 2 adder ADD1 and that, initially, the digits stored in the stages SR1-SR4 of the register are 1, 0, 0, 1 respectively as shown in Table I. The bits "0" and "1" stored in stages SR3 and SR4 of the register are combined in the adder ADD1 to yield a bit "1" which is fed to the shift register input.
The register is advanced by pulses from a clock source and, on receipt of the first advance pulse the bits stored in register stages SR1, SR2 and SR3 are fed to stages SR2, SR3 and SR4 respectively, and the bit "1" from the modulo 2 adder is fed to register stage SR1 Bits "0" and "0" which are now stored in register stages SR3 and SR4 are combined in the adder ADD1 to yield a bit "0" which is fed to the register input. Upon receipt of the next advance pulse the process is repeated, and it will be seen that in the resultant output pattern (once the pattern is established) each bit is the modulo 2 sum of the third and fourth preceding bits, unless an error has been introduced.
Table I ______________________________________ Shift Register SRI ADDI Shift Register SR1 SR2 SR3 SR4 Output (SR1) Output ______________________________________ 1 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 etc. ______________________________________
The use of a four stage shift register has been described by way of example only and it will be appreciated that registers having other numbers of stages could be employed and also that the inputs to the adder ADD1 need not be from adjacent register stages.
The error detecting apparatus (FIG. 2) also includes a shift register SRII, but this register has, for a purpose which will be explained below, (n + 1) stages: SR1, SR2 . . . SRr, SR(r + 1) . . . SRn, SR(n + 1). The (r + 1)th and the (n + 1)th stages have outputs to a modulo 2 adder ADD2 the output of which is applied, together with the output of the first stage of the register, to a correlator CLTR (for example, a further modulo 2 adder). The correlator compares the inputs and generates an output signal when the inputs are not the same.
The pseudo-random pattern from the apparatus of FIG. 1 is fed (in the form in which it is received at the receiver of the transmission system) to the shift register SRII. Under conditions of no error, the modulo 2 sum of the digits which at any one time are stored in stage SR(r + 1) and SR(n + 1) of register SRII should correlate with the digit stored in the first stage of the register, since this was the manner in which the pattern was generated in the apparatus of FIG. 1. If there is no correlation an error is present, and an output signal is generated by the correlator CLTR.
The use of n + 1 stages in the shift register SRII is not essential: a register have n stages could be used, with the adder ADD2 receiving the output of the rth and nth stages (instead of the (r + 1)th and (n + 1)th stages) and with the input to the register (instead of the output of the first stage) being applied to the correlator CLTR. In such an arrangement, however, it is advisable to include a buffer stage between the input to the register SRII and the correlator CLTR to ensure that no distorted pulses are fed to the correlator. When a register SII having (n + 1) stages is used, the first stage of the register itself acts as a buffer stage to ensure that undistorted, correctly clocked signals are fed to the correlator.
The particular arrangement of error detecting gates (that is, modulo 2 adder ADD2 and correlator CLTR) shown in FIG. 2 is not the only arrangement that could be utilized to detect errors in a digital pattern generated in the apparatus of FIG. 1. Other gating arrangements having the same functional effect as the gates ADD2 and CLTR (that is, the comparison of the output of the first stage of the shift register SRII with the modulo 2 sum of the outputs of the (r + 1)th and (n + 1)th stages) could be employed.
The function of the error-detecting apparatus shown in FIG. 2 is illustrated, by way of example, in Tables II and III set out below. In this case, it is assumed that the apparatus is to be employed with pattern generating apparatus as described above with reference to Table I. Accordingly since n = 4, the shift register SRII has 5 stages, the fourth and fifth stages having outputs to the modulo 2 adder ADD2. It is also assumed that the shift register SRI generates the output pattern specified in Table I.
Table II ______________________________________ Shift Register SRII Shift Register ADD2 SRII Input SR1 SR2 SR3 SR4 SR5 Output ______________________________________ 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 etc. ______________________________________
Table II illustrates the function of the error detecting apparatus in the absence of bit error. When the first bit from the output of shift register SRI, which is a "1" reaches the fifth stage of register SRII, the following "0" is in the fourth stage so that the output of the modulo 2 adder is a bit "1". This is compared by the correlator CLTR with the bit stored in the first stage of register SRII, which as shown in Table II is in the absence of errors, also a "1". The correlator, accordingly, does not generate an error signal.
The register SRII is advanced by pulses from a clock source and, on receipt of the next advance pulse, the bits stored in stages SR1 to SR4 of register SRII are fed to stages SR2 to SR5 and the next bit in the pattern generated by the FIG. 1 apparatus is fed to stage SR1. As shown in Table II, there is now a "0" in each of stages SR4 and SR5 so that the adder ADD2 yields the bit "0". The bit stored in stage SR1 of the register is now also a "0" so that the correlator CLTR again produces no output.
Table III ______________________________________ Shift Register SRII Shift Register Add 2 SRII Input SR1 SR2 SR3 SR4 SR5 Output ______________________________________ 0 1 1 0 0 1 1 0(c.sub.1) 0 1 1 0 0 0 0 o(c.sub.1) 0 1 1 0 1 Error 1 0 o(c.sub.1) 0 1 1 0 1 1 0 0(c.sub.1) 0 1 1 1 1 1 0 0(c.sub.1) 0 0 Error 0(c.sub.2) 1 1 1 0 0(c.sub.1) 0 Error 0 0(c.sub.2) 1 1 1 0 1 Error 0 0 0(c.sub.2) 1 1 1 0 0 0 0 0(c.sub.2) 1 1 0 1 0 0 0 0(c.sub.2) 1 1 Error 0 1 0 0 0 0(c.sub.2) 0 Error 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 etc. ______________________________________
Table III indicates the function of the error detector when two bits in the data pattern are received incorrectly as "0" instead of "1". The errors are indicated in Table III by the symbols (c.sub.1) and (c.sub.2). When the first error (c.sub.1) reaches the stage SR1 of the register, there is a bit "1" stored in the stage SR4 and a bit "0" stored in the stage SR5 so that the output of adder ADD2 is a bit "1". At this time the error bit "0" is stored in stage SR1 of the register so that there is no correlation between the inputs to the correlator CLTR which therefore produces an error signal.
It can be seen from a consideration of Table III that, provided the errors are so widely spaced that there is only one bit error in the register SRII at a time, each error will cause the correlator to generate three error signals (resulting from the passage of the error through stages SR1, SR4 and SR5 of the register). In view of this, the error detector includes, in addition to the correlator CLTR, a divide by three circuit DIV which generates an output signal in response to every three error signals generated by the correlator. The output of the divide circuit DIV is fed to a counter (not shown) to obtain a measurement of the bit error rate in the transmission system. Alternatively, the production of three error signals by a single error could be eliminated by including a modulo 2 adder between stages SR1 and SR2 in the shift register SRII and applying the output of the correlator CLTR to this adder together with the received pattern from the shift register stage SR1. The generation of an error signal by the correlator CLTR will then result in correction of the erroneous input digit to the shift register stage SR2 with the result that no further error signals will be caused by that digit.
It can be shown, if the bit errors in the pattern received by the FIG. 2 apparatus are assumed to be statically independent, that the bit error rate as measured at the output of the divide circuit DIV (that is, the mean error rate approximates very closely to the actual rate when the probability of bit error is low: for example, the measurement accuracy is about 98% for a bit error probability of 0.01, dropping to about 60% for a bit error probability of 0.25. These measurement accuracies are comparable (except at very high error rates) with those that can be achieved with conventional error detector involving the local generation (at the receiver) of a test pattern and comparison of the test and received patterns. However, conventional detectors involve complex equipment to synchronize the test and received patterns and may lose synchronization at high error rates whereas apparatus of the type shown in FIG. 2 provides a continuously synchronized error detector which is not affected by error rate.
If bit errors occur in blocks, instead of singly as assumed in Table III, then the measurement accuracy may be reduced. This is illustrated in Table IV which is similar to Table II and III but includes a block of three bit errors (c.sub.1), (c.sub.2) and (c.sub.3).
Table IV ______________________________________ Shift Register (SRII) Shift Register ADD2 (SRRII) Input SR1 SR2 SR3 SR4 SR5 Output ______________________________________ 1(c.sub.1) 1 1 0 0 1 1 0(c.sub.2) 1(c.sub.1) 1 1 0 0 0 Error 1(c.sub.3) 0(c.sub.2) 1(c.sub.1) 1 1 0 1 Error 1 1(c.sub.3) 0(c.sub.2) 1(c.sub.1) 1 1 0 Error 1 1 1(c.sub.3) 0(c.sub.2) 1(c.sub.1) 1 0 Error 1 1 1 1(c.sub.3) 0(c.sub.2) 1(c.sub.1) 1 1 1 1 1 1(c.sub.3) 0(c.sub.2) 1 0 1 1 1 1 1(c.sub.3) 0 Error 0 0 1 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 1 0 1 ______________________________________
Since the presence of one error sometimes cancels out the presence of another, only five error signals are generated by the correlator CLTR whereas nine signals would have been generated if the errors had passed through the register SRII singly. A similar effect may occur if the spacing between bit errors is, for example, (referring to FIGS. 1 and 2) r or n or n-r.
It has been found that blocks of statistically-independent errors do not have a significant effect on the accuracy of the long-term mean error rate as measured at the output of the divide circuit DIV (FIG. 2), but if it is wished to measure the block errors themselves then measurement accuracy can be increased (as least as regards bit errors occurring in blocks of two) by spacing the rth and nth stages of the registers SRI, SRII apart by at least one stage. As the spacing between the rth and nth stages, and also the value of r is increased further, so the apparatus becomes more alert to longer blocks of bit errors.
A further advantage of spacing the rth and nth stages of registers SRI, SRII apart by at least one stage is that errors occurring in coherent pairs can be detected. Coherent pairs of errors are errors which occur simultaneously in adjacent bits of a digital stream and are not statistically independent. Such errors can arise when the digital stream is transmitted by modulation onto a carrier, depending on the method of modulation/demodulation that is used. One method which can give rise to coherent pairs of errors is phase coherent modulation/demodulation with differential coding/decoding: in this system, the phase of any one bit is compared with the phase of the previous bit with the result that a single error in the coded pulse stream causes simultaneous errors in adjacent bits of the decoded pulse stream. It has been found that apparatus as shown in FIGS. 1 and 2 (with n--r)&gt;)1 can detect these coherent pairs of errors with similar accuracy to that associated with the detection of single errors, and as the spacing (n--r) is increased so the apparatus becomes more alert to errors in larger coherent blocks.
It will be appreciated from the above description that the form of the error detecting apparatus is dependent upon the form of the pseudo-random pattern transmitted over the system, and that the arrangement shown in FIG. 1 could be replaced by other pseudo-random pattern generators with appropriate modifications being made to the detector of FIG. 2. The general arrangement shown in the drawing is, however, preferable on the ground of simplicity, particularly advantageous arrangements (as regards the detection of block errors) being those in which the pattern generator (FIG. 1) has 9 stages with a modulo 2 feed back from stages 5 and 9 (i.e. n = 9, r = 5) and 18 stages with a modulo 2 feed back from stages 11 and 18 (i.e., n = 18, r = 11).